/*
 * @lc app=leetcode id=33 lang=cpp
 *
 * [33] Search in Rotated Sorted Array
 */
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int i = 0;
        int j = len-1;
        int mid;

        while (i <= j) {
            mid = (i+j)/2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] <= nums[j]) {
                if (target > nums[mid] && target <= nums[j]) {
                    i = mid+1;
                } else {
                    j = mid-1;
                }
            } else {
                if (target >= nums[i] && target < nums[mid]) {
                    j = mid-1;
                } else {
                    i = mid+1;
                }
            }
        }
        return -1;
    }
};

